package com.lw.leetcode.dp.b;

/**
 * 673. 最长递增子序列的个数
 *
 * @Author liw
 * @Date 2021/9/20 9:33
 * @Version 1.0
 */
public class FindNumberOfLIS {


    public static void main(String[] args) {
        FindNumberOfLIS test = new FindNumberOfLIS();
        int[] arr = {1};
//        int[] arr = {1,3,5,4,7};
//        int[] arr = {2,2,2,2,2};
//        int[] arr = {1,2,4,3,5,4,7,2};
        int numberOfLIS = test.findNumberOfLIS(arr);
        System.out.println(numberOfLIS);
    }

    public int findNumberOfLIS(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return length;
        }
        int[] arr = new int[length];
        int[] counts = new int[length];
        arr[0] = 1;
        counts[0] = 1;
        int m = 0;
        for (int i = 1; i < length; i++) {
            int v = nums[i];
            int max = 0;
            int limt = 0;
            for (int j = i - 1; j >= limt; j--) {
                if (v > nums[j]) {
                    max = Math.max(max, arr[j]);
                    limt = max - 1;
                }
            }
            int c = 0;
            for (int j = i - 1; j >= limt; j--) {
                if (v > nums[j] && max == arr[j]) {
                    c += counts[j];
                }
            }
            counts[i] = c == 0 ? 1 : c;
            arr[i] = max + 1;
            m = Math.max(m, max + 1);
        }
        int c = 0;
        for (int i = 0; i < length; i++) {
            if (arr[i] == m) {
                c += counts[i];
            }
        }
        return c;
    }

}
